#include <algorithm>
#include <bits/stdc++.h>
#include <csignal>
using namespace std;

//双指针

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        if(nums.size()<4) return ans;
        sort(nums.begin(), nums.end());
        int len = nums.size();
        for(int first=0; first<len; ++first){
            if((long long)nums[first]+nums[first+1]+nums[first+2]+nums[first+3]>target) break;
            if(first > 0 && nums[first]==nums[first-1]) continue;
            for(int second=first+1; second<len; ++second){
                if((long long)nums[first]+nums[second]+nums[second+1]+nums[second+2]>target) break;
                if(second > first+1 && nums[second]==nums[second-1]) continue;
                int third = second+1;
                int fourth = len - 1;
                while(third < fourth){                  
                    long long sum = nums[first];
                    sum +=nums[second];
                    sum +=nums[third];
                    sum +=nums[fourth];
                    if(target < sum) --fourth;
                    if(target > sum) ++third;
                    if(target == sum){
                        ans.push_back({nums[first], nums[second], nums[third], nums[fourth]});
                        while(third < fourth && nums[third] == nums[third+1]) ++third;
                        ++third;
                        while(fourth > third && nums[fourth] == nums[fourth-1]) --fourth;
                        --fourth;
                    }
                }
                
            }
        }
        return ans;
    }
};

int main(){
    vector<int> vec = {0,0,0,0};
    Solution solution;
    solution.fourSum(vec, 0);
    return 0;
}